Network communications commonly make use of packet switching techniques to route data over a shared network. The principle of “packet switching” generally involves dividing data traffic into individual segments, or packets, and assigning a destination address to each packet. The packets are then directed (e.g. routed or switched) through the network according to the packet's destination address by way of a router.
Routing data through a network typically involves forwarding packets between connected network hosts, connected resources or other connected networks. There are several commonly used networking protocols which are used to manage the routing of the data, example protocols include: Ethernet, Multi-protocol Label Switching (MPLS), Asynchronous Transfer Mode (ATM) and Internet Protocol (IP). It is to understood that the term “routing” is used herein to relate to the forwarding and transmission of data packets on any type of communications network and therefore is intended to include at least both Switched (Ethernet) and Routed (IP) Networks. Moreover, any references to a “router” are to be taken to include both IP routers and Ethernet Switches, and thus the routing of packets by way of such devices is to be construed accordingly.
Most routers forward packets by applying a lookup mechanism, typically a lookup algorithm, to each received packet in order to determine the routing information for that packet based on its destination address. The routing information is generally maintained within a searchable data structure, which contains information about each of the hosts, resources and other networks connected to the communications network. In Ethernet-based networks, Ethernet Switches perform routing by implementing lookup algorithms that usually make use of “exact match” searches.
There are four main techniques in the prior art for achieving an exact match search, and consequently exact match lookup algorithms are usually based on one of the following: (1) Direct Lookup, (2) Associative Lookup, (3) Hashing and (4) Binary Search.
Although Direct Lookup techniques may be successfully used in conjunction with MPLS or ATM packet switching, it is generally not possible to use this technique with Ethernet Switching as the destination address (i.e. the MAC-destination address) is 48-bits in length. In practice, this means that the searchable data structure cannot hold all the addresses, as the dimension of the structure is usually much smaller than 248.
Associative Lookup is based on associative memory, also commonly referred to as “Content Addressable Memory” (CAM), that compares all stored addresses to the destination address of the received packet. The comparison involves searching every memory location in parallel until a match is found, whereupon the address of the location that contains the required information is returned. Associative memory has a low latency (typically comparable to SRAM), while providing an increased search speed (due to a lower number of required memory accesses). However, despite its advantages CAM has a very low density compared to both DRAM and SRAM, and the cost per bit is generally quite expensive in comparison to other memory types. Moreover, due to the parallel operation of the CAM, the power dissipation is found to be quite high compared to conventional RAM, and therefore its use is found to be less suitable for cost-sensitive applications.
A lookup algorithm based on Hashing involves mapping a 48-bit destination address into an n-bit address, where n<<48 (e.g. n=16). The data structure may then be searched linearly (or possibly via a binary search—see below) in order to locate the required information for routing the packet. Although the Hashing technique is simple to implement, it is necessary to manage collisions between conflicting hashed destination addresses, with the resulting lookup being non-deterministic, i.e. the technique gives rise to an unpredictable number of memory accesses.
The Binary Search technique requires the use of a searchable data structure having the form of a binary search tree. The lookup algorithm locates routing information within the structure by carrying out a binary search, which begins by comparing a packet's destination address (i.e. input key) against the address corresponding to the root of the tree.
Depending on the result of the comparison, the binary search proceeds to select a branch in the tree leading to the next address (corresponding to a node within the tree) that is to be compared to the input key. The process continues by descending through subsequent branches and carrying out corresponding comparisons until the required information is found. Despite binary search trees having update and scalability drawbacks, such structures are known to be very storage-efficient, while being simple to implement and search. Moreover, the height of a binary search tree (i.e. as gauged by the number of different branched levels between the root and lowest nodes) may be readily reduced by simply rearranging the structure of the tree.
The simple structure of a binary search tree enables searching to be deterministic, and therefore the number of required memory accesses may be known beforehand or estimated with a high degree of reliability, in contrast to searches carried out by Hashing lookup algorithms. As a result, most lookup algorithms used in present-day data routing are based on binary searches, but their principle drawback is the relatively poor scalability in terms of their search (lookup) speed, as increasingly larger structures take more time to search.